import java.util.HashMap;
import java.util.Map;

/**
 * 166. 分数到小数
 * https://leetcode-cn.com/problems/fraction-to-recurring-decimal/
 */
public class Solutions_166 {
    public static void main(String[] args) {
//        int numerator = 1, denominator = 2;  // output: "0.5"
//        int numerator = 2, denominator = 1;  // output: "2"
//        int numerator = 2, denominator = 3;  // output: "0.(6)"
//        int numerator = 4, denominator = 333;  // output: "0.(012)"
//        int numerator = 1, denominator = 5;  // output: "0.2"
//        int numerator = 1, denominator = 6;  // output: "0.1(6)"
//        int numerator = 0, denominator = 3;  // output: "0"
        int numerator = -1, denominator = -2147483648;  // output: "0.0000000004656612873077392578125"

        String result = fractionToDecimal(numerator, denominator);
        System.out.println(result);
    }

    /**
     * 解题思路：哈希表 + 数学
     */
    public static String fractionToDecimal(int numerator, int denominator) {
        // 特殊情况：被除数为 0，以及除数为 1
        if (numerator == 0) {
            return "0";
        }
        if (denominator == 1) {
            return String.valueOf(numerator);
        }
        StringBuilder sb = new StringBuilder();
        if ((numerator >= 0) ^ (denominator >= 0)) {
            // 一个为正数，一个为负数时，除数也为负数
            sb.append("-");
        }
        // 转换成 long 型的正整数
        long num1 = Math.abs((long) numerator);
        long num2 = Math.abs((long) denominator);
        sb.append(num1 / num2);
        if (num1 % num2 == 0) {
            // 能够整除
            return sb.toString();
        }
        // 开始计算小数部分
        sb.append('.');
        // 记录被除数是否出现，以及位于 sb 字符串的下标
        Map<Long, Integer> map = new HashMap<>();

        long remind = num1 % num2;
        // 若被除数出现过，说明将无限循环
        while (remind > 0 && !map.containsKey(remind)) {
            // 记录下被除数对应的下标
            map.put(remind, sb.length());
            // 不够除，乘 10
            remind = (remind % num2) * 10;
            // 乘 10 后，再除
            sb.append(remind / num2);
            // 取相除之后的余数
            remind = remind % num2;
        }
        if (remind == 0) {
            // 没有出现循环的小数
            return sb.toString();
        }
        // 在重复的被除数之前，插入开括号
        int insertIndex = map.get(remind);
        sb.insert(insertIndex, "(");
        sb.append(")");
        return sb.toString();
    }
}
